import java.util.*;
import java.util.concurrent.BlockingDeque;
import java.util.concurrent.LinkedBlockingDeque;

public class project {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> list=new ArrayList<>();
        Map<Integer,Integer> map=new HashMap<>();
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        int len=nums.length/3;
        for(Map.Entry<Integer,Integer> entry: map.entrySet()){
            if(len<entry.getValue()){
                list.add(entry.getKey());
            }
        }
        return list;
    }















    public int lengthOfLIS(int[] nums) {
        int len=nums.length;
        int[] dp=new int[len];
        dp[0]=1;
        int max=0;
        for(int i=1;i<len;i++){
            dp[i]=1;
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            max=Math.max(max,dp[i]);
        }

        return max;
    }

















    public boolean isValidSerialization(String preorder) {
        int len=preorder.length();
        int count=1;
        int index=0;
        while (index<len){
            if (count==0){
                return false;
            }
            if(preorder.charAt(index)==','){
                index++;
            } else if (preorder.charAt(index) == '#') {
                count--;
                index++;
            }else{
                while (index<len&&preorder.charAt(index)!=','){
                    index++;
                }
                count++;
            }
        }
        return count==0;
    }










    public int findMinArrowShots(int[][] points) {
        if(points.length==0){
            return 0;
        }
        Arrays.sort(points,(p1,p2)->p1[1]<p2[1]?-1:1);
        int ret=1;
        int prev=points[0][1];
        for(int i=1;i<points.length;i++){
            if(points[i][0]>prev){
                ret++;
                prev=points[i][1];
            }
        }
        return ret;
    }















    public int calPoints(String[] ops) {
        Stack<Integer> stack=new Stack<>();
        int count=0;
        for(String s:ops){
            if(s.equals("+")){
                int x=stack.pop();
                int y=stack.peek();
                stack.push(x);
                stack.push(x+y);
            }else if(s.equals("D")){
                int tmp=stack.peek();
                stack.push(tmp*2);
            }else if(s.equals("C")){
                stack.pop();
            }else{
                stack.push(Integer.parseInt(s));
            }
        }
        while (!stack.isEmpty()){
            count+=stack.pop();
        }
        return count;
    }


}
